﻿// 迷宫问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//注意，以后不清楚的情况不要用++了！！！！！
#include<stdio.h>
#include<stdlib.h>
typedef struct Sqstack {//存储栈的头尾指针与最大值
	int* headptr, * tailptr;
	int maxisize;//指栈的最大元素个数，在不重复通过某路径的情况下，其为所有路径个数之和
}Sqstack;
int readtxt(int** a, FILE* fp, Sqstack* Sq, int MAX) {//读取联通的路径并计算栈的最大值
	Sq->maxisize = 0;
	int j, i;//用于读取路径
	while (!feof(fp)) {
		fscanf(fp, "%d %d", &i, &j);
		a[i][j] = 1; a[j][i] = 1;
		Sq->maxisize++;
	}
	return 0;
}
int find(int** a, Sqstack* Sq, int MAX, int *end) {//找到且输出所有可行的路径
	int i = *(Sq->tailptr), j = 1,*minroute,min=Sq->maxisize;//i指当前节点，j指下一个点,minroute为最短路径，min为其长度
	if (!(minroute = (int*)malloc(sizeof(int)*Sq->maxisize))) exit(1);//是否成功分配内存
	while (Sq->headptr <= Sq->tailptr) {//如果已经遍历了所有可能的路径（栈为空），结束循环
		for (;j <= MAX;) {//寻找下一个节点,没有相通的下一个节点或走出迷宫结束
			if (a[i][j] == 1) {
				a[i][j] = 0; a[j][i] = 0;//走过这条路径，将其锁死
				Sq->tailptr = Sq->tailptr + 1;
				*(Sq->tailptr) = j;
				for (int l = 1;end[l] != -1;l++) {
					if (j == end[l]) {//走出了迷宫，输出路径
						int k = 0;//k是当前路径的长度
						printf("路径：");
						for (int* begin = Sq->headptr;begin <= Sq->tailptr;begin++, k++)
							printf("%d ", *begin);
						printf("长度：%d\n", k);
						if (k < min) {
							int a = 0;
							for (int* begin = Sq->headptr;begin <= Sq->tailptr;begin++, a++)
								minroute[a] = *begin;
							minroute[a] = -1;
							k = min;
						}
						goto go_out;//走出迷宫，出栈
					}
				}
					i = j; j = 1;//未到达终点，将节点入栈（maxisize的值一定大于可能的路径个数，不用判满）
			}
			else j++;
		}
go_out:
		j = *(Sq->tailptr) + 1;
		(Sq->tailptr)--;//出栈一个已经经过的点作为寻找下一个节点的循环的起始点
		if (Sq->headptr <= Sq->tailptr)
			i = *(Sq->tailptr);
		a[i][j - 1] = 1; a[j - 1][i] = 1;//出站后将锁死的路径解封
	}
	printf("其中最短路径为：");
	for (int l = 0;minroute[l] != -1;l++)
		printf("%d ", minroute[l]);
	printf("\n最短长度为：%d", min);
	return 0;
}
int main() {
	int** a, MAX, start, *end;//a是指向用来储存路径的二维动态数组的指针，在这个数组中若i与j联通则a[i][j]==a[j][i]==1,MAX是指节点总数,start,end为起始点与终点
	FILE* fp;//通过fp打开文件
	Sqstack* Sq;
	if (!(Sq = (Sqstack*)malloc(sizeof(Sqstack)))) exit(1);//是否成功分配内存
	if ((fp = fopen("test.txt", "r")) == NULL) exit(1);//是否成功打开文件
	fscanf(fp, "%d", &MAX);
	if (!(a = (int**)malloc(sizeof(int*) * (MAX + 1))))  exit(1);//是否成功分配内存
	for (int i = 0; i <= MAX; ++i)
	{
		if (!(a[i] = (int*)malloc(sizeof(int) * (MAX + 1))))  exit(1);//是否成功分配内存
		for (int j = 0; j <= MAX; ++j)
			a[i][j] = 0;
	}//上述步骤创造用来储存路径的二维动态数组,且只能在主函数中创建
	end = (int*)malloc(sizeof(int)* MAX);
	end[0] = 0;
	scanf("%d", &start);
	for (int i = 1;end[i-1] != -1;i++)
		scanf("%d", &end[i]);//出口的输入以-1作为结束符
	readtxt(a, fp, Sq, MAX);
	if (!(Sq->headptr = (int*)malloc(sizeof(int) * Sq->maxisize)))exit(1);//是否成功创建栈
	*(Sq->headptr) = start; Sq->tailptr = Sq->headptr;
	find(a, Sq, MAX, end);
	fclose(fp);
	free(Sq);
	return 0;
}
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
